#include <stdio.h>
#include <stdlib.h>
#include "crosslist.h"
//十字链表只需将行列分成两个链表,进行单链表操作即可
int init_cross_list(PCrossList L, const ElemType *A, int m,int n){
    L->rowhead=(OLink*)malloc((m+1)*sizeof(OLNode));//初始化L
    L->colhead=(OLink*)malloc((n+1)*sizeof(OLNode));
    L->rows=m;
    L->cols=n;
    L->nums=0;
    for(int i=0;i<=m;i++){
        L->rowhead[i]=NULL;
    }
    for(int j=0;j<=n;j++){
        L->colhead[j]=NULL;
    }
    int k=0;
    while(k<m*n){
        if(A[k]!=0){
            OLNode *p=(OLNode*)malloc(sizeof(OLNode));
            p->down=NULL;
            p->right=NULL;
            p->row=k/n+1;//根据k确定非零值在十字链表中的位置
            p->col=k%n+1;
            p->value=A[k];
            L->nums++;
            if(L->rowhead[p->row]==NULL){//头结点非零
                L->rowhead[p->row]=p;
            }else{
                OLNode *q=L->rowhead[p->row];
                while(q->right!=NULL){//计算的结点位置从上到下,从左到右顺序排列,故直接接上
                    q=q->right;
                }
                q->right=p;
            }
            if(L->colhead[p->col]==NULL){//同行操作
                L->colhead[p->col]=p;
            }else{
                OLNode *q=L->colhead[p->col];
                while(q->down!=NULL){
                    q=q->down;
                }
                q->down=p;
            }
        }
        k++;
    }
    return L->nums;
}


int del_cross_list(PCrossList L, ElemType k) {
    int count = 0;
    for(int i=1;i<=L->rows;i++){//按行寻找k
        OLNode *p=L->rowhead[i];
        OLNode *pre_row=NULL;
        while(p!=NULL){//本行不为空,有结点
            if(p->value!=k){
                pre_row=p;
                p=p->right;
            }else{
                if(p==L->rowhead[i]){//行头结点为k
                    L->rowhead[i]=p->right;
                }else{
                    pre_row->right=p->right;
                }
                OLNode *q=L->colhead[p->col];//列操作,使列链表连续
                OLNode *pre_col=NULL;
                while(q!=p){
                    pre_col=q;
                    q=q->down;
                }
                if(q==L->colhead[p->col]){
                    L->colhead[p->col]=q->down;
                }else{
                    pre_col->down=q->down;
                }
                OLNode *temp=p;
                p=p->right;//p沿行后移
                count++;
                L->nums--;
                free(temp);//不可直接free(p),否则while循环出问题
            }
        }
    }
    return count;
}